package com.justnow.offer;

/**
 * 中心扩散方法
 */
public class Solution5_1 {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;

        char[] charArray = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            int oddLen = expandAroundCenter(charArray, i, i);
            int evenLen = expandAroundCenter(charArray, i, i + 1);

            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                begin = i - (maxLen - 1) / 2;
            }
        }

        //subString 左闭右开的原因
        return s.substring(begin, begin + maxLen);
    }

    /**
     *
     * @param charArray
     * @param left
     * @param right
     * @return
     */
    private int expandAroundCenter(char[] charArray, int left, int right) {
        //left = right 的时候, 此时回文中心是一个字符,回文串的长度是奇数
        //right = left + 1的时候,此时回文中心是一个空隙,回文串的长度是偶数
        //跳出循环的条件是 charArray[left] != charArray[right]
        while (left >= 0 && right < charArray.length && charArray[left] == charArray[right]) {
            left--;
            right++;
        }
        //此时right是回文字符串后面的一个下标, left是回文字符串前面一个元素的下标
        return right - left - 1;
    }
}
